package util;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : DoubleList.java
 * @Author : WangRuoyu
 * @Date 2023/11/19 22:48
 */


public class DoubleList {
    DoubleListNode head;
    DoubleListNode tail;

    public DoubleList() {
        head = new DoubleListNode(-1);
        tail = new DoubleListNode(-1);
        head.next = tail;
        tail.pre = head;
    }

    public boolean isEmpty() {
        return head.next == tail;
    }

    /***
     * 头插法插入数据
     * ***/
    public void insertFromHead(int x) {
        DoubleListNode tmp = new DoubleListNode(x);
        tmp.next = head.next;
        tmp.pre = head;
        head.next.pre = tmp;
        head.next = tmp;
    }

    /***
     * 尾插法插入数据
     * ***/
    public void insertFromTail(int x) {
        DoubleListNode tmp = new DoubleListNode(x);
        tmp.pre = tail.pre;
        tmp.next = tail;
        tail.pre.next = tmp;
        tail.pre = tmp;
    }

    /***
     * 删除第一个数据
     * ***/
    public DoubleListNode deleteFromHead() {
        if (isEmpty()) return null;
        DoubleListNode tmp = head.next;
        head.next = head.next.next;
        head.next.pre = head;
        return tmp;
    }

    /***
     * 删除最后一个数据
     * ***/
    public DoubleListNode deleteFromTail() {
        if (isEmpty()) return null;
        DoubleListNode tmp = tail.pre;
        tail.pre = tail.pre.pre;
        tail.pre.next = tail;
        return tmp;
    }

    /***
     * 删除第k个数据
     * ***/
    public DoubleListNode deleteK(int k) {
        if (k < 1) return null;
        DoubleListNode p = head;
        for (int i = 0; p != null && i < k - 1; i++, p = p.next) {
            if (p.next == tail) return null;
        }
        DoubleListNode tmp = p.next;
        p.next = p.next.next;
        p.next.pre = p;
        return tmp;
    }

    /***
     * 删除值为x的数据
     * ***/
    public DoubleListNode deleteValueofX(int x) {
        if (isEmpty()) return null;
        for (DoubleListNode p = head; p != tail; p = p.next) {
            if (p.val == x) {
                p.pre.next = p.next;
                p.next.pre = p.pre;
                return p;
            }
        }
        return null;
    }

    /***
     * 输出双向链表
     * ***/
    public void printDoubleList() {
        for (DoubleListNode p = head.next; p != tail; p = p.next) {
            System.out.println(p.val + " ");
        }
        System.out.println();
    }
}

